/*
 * @lc app=leetcode.cn id=807 lang=typescript
 *
 * [807] 保持城市天际线
 */

// @lc code=start
function maxIncreaseKeepingSkyline(grid: number[][]): number {
  const n = grid.length;
  const rowMax = new Array(n).fill(0);
  const colMax = new Array(n).fill(0);

  // 记录每行、每列的最大值
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      rowMax[i] = Math.max(rowMax[i], grid[i][j]);
      colMax[j] = Math.max(colMax[j], grid[i][j]);
    }
  }

  let ans = 0;
  // 计算每个房子可以增加的最大值
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 可以增加的最大值 = 当前行列的最小高度 - 当前房子的高度
      ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
    }
  }

  return ans;
}
// @lc code=end
